void sort(int arr[], int low, int hi);
void merge(int arr[], int low, int mid, int hi);

void sort(int arr[], int low, int hi) {
    if (low < hi) {
        int mid = (low + hi) / 2;
        sort(arr, low, mid);
        sort(arr, mid + 1, hi);
        merge(arr, low, mid, hi);
    }
}

void merge(int arr[], int low, int mid, int hi) {
    int i = low, j = mid + 1, k = 0;
    int tmp[hi - low + 1];
    while (i <= mid && j <= hi) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    while (j <= hi) {
        tmp[k++] = arr[j++];
    }
    k--;
    while (k >= 0) {
        arr[low + k] = tmp[k];
        k--;
    }
}